#include "headfiles.h"


int maxProduct(int A[], int n) {
    if (n <= 0) {
        return 0;
    }
    
    if (n == 1) {
        return A[0];
    }
    
    int i, j;
    int num_negatives = 0;
    int max_product = -1;
    int product = 1;
    int max_start, max_end, start;
    start = 0;
    for (i = 0; i < n; i++) {
        if (A[i] == 0) {
            product = 1;
            if (max_product < 0) {
                max_product = 0;
            }
            start = i + 1;
            continue;
        }
        
        product *= A[i];
        if (product > 0) {
            if (product > max_product) {
                max_product = product;
                max_start = start;
                max_end = i;
            }
        }
        // For negative product, find a start location
        // that can produce a positive number
        else {
            int sub_product = product;
            for (j = start; j < i; j++) {
                sub_product /= A[j];
                if (sub_product > 0) {
                    if (sub_product > max_product) {
                        max_product = sub_product;
                        max_start = j;
                        max_end = i;
                    }
                    
                    break;
                }
            }
        }
    }
    
    return max_product;
}
